package com.burns.leetcode.d508t;

import java.util.*;

/**
 * 给你一个二叉树的根结点 root ，请返回出现次数最多的子树元素和。如果有多个元素出现的次数相同，返回所有出现次数最多的子树元素和（不限顺序）。
 * <p>
 * 一个结点的 「子树元素和」 定义为以该结点为根的二叉树上所有结点的元素之和（包括结点本身）。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/most-frequent-subtree-sum
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Main {
    public static void main(String[] args) {
        TreeNode root = initData();
        int[] frequentTreeSum = findFrequentTreeSum(root);
        System.out.println(frequentTreeSum);
        for (int i = 0; i < frequentTreeSum.length; i++) {
            System.out.print(frequentTreeSum[i] + "、");

        }
    }

    private static TreeNode initData() {
        TreeNode leftLeft = new TreeNode(1);
        TreeNode left = new TreeNode(14, leftLeft, null);
        TreeNode root = new TreeNode(5, left, null);

        return root;
    }

    public static int[] findFrequentTreeSum(TreeNode root) {
//        Map<Integer,Integer> valAndNumMap = new HashMap<>();
        List<Integer> resultList = new ArrayList<>();
//        handle(valAndNumMap,root);
        handleList(resultList, root);
//        int maxVal = getMaxValue(valAndNumMap);
//        Set<Map.Entry<Integer, Integer>> entries = valAndNumMap.entrySet();
//        for(Map.Entry<Integer,Integer> entry:entries){
//            if(maxVal==entry.getValue()){
//                resultList.add(entry.getKey());
//            }
//        }

        Map<Integer, Integer> valAndCountMap = new HashMap<>();
        for (Integer i : resultList) {
            Integer count = valAndCountMap.get(i);
            if (count == null) {
                valAndCountMap.put(i, 1);
            } else {
                valAndCountMap.put(i, count + 1);
            }
        }
        int maxCount = getMaxCount(valAndCountMap);
        Set<Integer> resultSet = new HashSet<>();
        if (maxCount == 1) {
            for (Integer i : resultList) {
                resultSet.add(i);
            }
        } else {
            Set<Map.Entry<Integer, Integer>> entries = valAndCountMap.entrySet();
            for (Map.Entry<Integer, Integer> entry : entries) {
                if (entry.getValue() == maxCount) {
                    resultSet.add(entry.getKey());
                }
            }
        }


        int[] result = new int[resultSet.size()];
        Iterator<Integer> resultSetIterator = resultSet.iterator();
        for (int i = 0; i < resultSet.size(); i++) {
            result[i] = resultSetIterator.next();
        }

        return result;


    }

    private static void handleList(List<Integer> resultList, TreeNode root) {
        if (root != null) {
            resultList.add(sum(new Data(0), root));
            if (root.left != null) {
//                resultList.add(sum(new Data(0), root.left));
                handleList(resultList, root.left);
            }

            if (root.right != null) {
//                resultList.add(sum(new Data(0), root.right));
                handleList(resultList, root.right);
            }
        }
    }

    private static Integer sum(Data data, TreeNode root) {
        if (root != null) {
            data.val += root.val;
            if (root.left != null) {
                data.val+=sum(new Data(0), root.left);
            }
            if (root.right != null) {
                data.val+=sum(new Data(0), root.right);
            }
        }
        return data.val;


    }

    private static int getMaxCount(Map<Integer, Integer> valAndNumMap) {
        int maxVal = 0;
        Iterator<Integer> valIterator = valAndNumMap.values().iterator();
        while (valIterator.hasNext()) {
            Integer next = valIterator.next();
            if (maxVal < next) {
                maxVal = next;
            }
        }
        return maxVal;

    }
//
//    private static void handle(Map<Integer, Integer> valAndNumMap, TreeNode root) {
//        if(root!=null){
//            valAndNumMap.put(root.val,1);
//            if ((root.left != null || root.right != null)) {
//                if(root.left!=null){
//                    Integer leftNum = valAndNumMap.get(root.left.val);
//                    if(leftNum==null){
//                        valAndNumMap.put(root.left.val,1);
//                    }else {
//                        valAndNumMap.put(root.left.val,leftNum+1);
//                    }
//                    handle(valAndNumMap,root.left);
//                }
//
//                if(root.right!=null){
//                    Integer rightNum = valAndNumMap.get(root.right.val);
//                    if(rightNum==null){
//                        valAndNumMap.put(root.right.val,1);
//                    }else {
//                        valAndNumMap.put(root.right.val,rightNum+1);
//                    }
//                    handle(valAndNumMap,root.right);
//                }
//            }
//        }
//    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Data {
    int val;

    public int getVal() {
        return val;
    }

    public void setVal(int val) {
        this.val = val;
    }

    public Data(int val) {
        this.val = val;
    }
}
